11401. Игра

В свободное время Фидан и Фуад играют дома. На этот раз они придумали такую игру:

· Фуад берет чистый лист бумаги.

· Фидан говорит одно число. Если это число написано на бумаге, Фуад стирает это число с бумаги, в противном случае, если оно не написано, Фуад записывает число на бумаге. Этот процесс повторяется n раз.

· В конце Фидан должна определить, сколько чисел написано на бумаге.

Числа Фидан a₁, a₂, ..., a_n заданы в том порядке, в котором она их сказала. В конце помогите Фидан найти количество чисел, написанных на бумаге.

Вход. Первая строка содержит одно целое число n (1 ≤ n ≤ 10⁵). Вторая строка содержит n целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).

Выход. Выведите сколько чисел оказались написанными на бумаге в конце игры.

Пример входа 1	Пример выхода 1
4 5 7 4 5	2
Пример входа 2	Пример выхода 2
6 1 2 3 2 3 1	0

РЕШЕНИЕ

структуры данных – set

Анализ алгоритма

Будем моделировать игру при помощи структуры данных множество (set). Множество хранит все числа, записанные на бумаге. При поступлении числа от Фидан, Фуад проверяет, содержится ли оно во множестве. Если содержится, то Фуад удаляет число из множества. Если не содержится, то добавляет число во множество.

Количество написанных чисел в конце игры равно количеству чисел во множестве.

Пример

Промоделируем работу множества для первого и второго примеров.

В конце игры:

· Первое множество содержит 2 элемента;

· Второе множество пустое (содержит 0 элементов);

Реализация алгоритма

Читаем количество чисел n.

scanf("%d", &n);

Последовательно обрабатываем n чисел, сказанных Фидан.

for (i = 0; i < n; i++)

{

scanf("%d", &x);

Фидан называет число x.

· Если числа x нет во множестве, то добавляем его туда.

· Если число x присутствует во множестве, то удаляем его туда.

if (s.find(x) == s.end())

s.insert(x);

else

s.erase(x);

}

Выводим ответ – размер множества.

printf("%d\n", s.size());